Міністерство освіти і науки України Національний Університет «Львівська Політехніка» Кафедра ЕОМ Контрольно-розрахункова робота з дисципліни «Прикладна теорія цифрових автоматів» (Частина І, завдання 5,6) 2005 1.5 Для шістнадцяти розрядного двійкового коду (1ц1л)(2ц1л)(1ц8л)(2ц8л) сформувати код Геммінга і продемонструвати його реакцію на однократний збій. Збій подати у вигляді таблиці. Варіант В3 Шістнадцяти розрядний двійковий код отриманий за допомогою кодової таблиці, згідно мого варіанту матиме наступний вигляд: 0011 1000 0011 0101 Код Геммінга належить до кодів, які дозволяють виправити помилки, що виникають при пересиланні інформації. При пересиланні інформації до і інформаційних розрядів додається k перевірочних розрядів так, що загальна довжина n слова, яке пересилається, становить n=i+k розрядів. У Таблиці 1 позначено: І-інформаційні розряди, які необхідно передати лінією; k- перевірочні розряди, які додаються до інформаційних передавачем інформації; n1..n21- розряди слова, яке передається; #- позначення операції додавання за модулем 2; Номер розряду, який передається, записується у таблиці в стовпчик у двійковому коді( старший розряд-верхній). Перевірочним розрядам відповідають ті графи таблиці, двійковий код яких має тільки одну 1.Вони знаходяться додаванням за модулем 2 тих інформаційних розрядів, які мають у своїй графі 1 на тому самому місці, що і відповідний перевірочний розряд. Таблиця 1 n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 n14 n15 n16 n17 n18 n19 n20 n21  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1  0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0  0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1  0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0  1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1  k1 k2 i3 k4 i5 i6 i7 k8 i9 i10 i11 i12 i13 i14 i15 k16 i17 i18 i19 i20 i21  0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1   k1=i3#i5#i7#i9#i11#i13#i15#i17#i19#i21=0#0#1#1#0#0#1#1#1#1=0 k2=i3#i6#i7#i10#i11#i14#i15#i18#i19=0#1#1#0#0#0#1#0#1=0 k4=i5#i6#i7#i12#i13#i14#i15#i20#i21=0#1#1#0#0#0#1#0#1=0 k8=i9#i10#i11#i12#i13#i14#i15=1#0#0#0#0#0#1=0 k16=i17#i18#i19#i20#i21=1#0#0#1#1=1 n=00000 1101 0000 0111 0101 Припустимо, що внаслідок помилки під час передачі інформації змінився розряд n3, тобто приймач отримав код: 00(1)00 1101 0000 0111 0101 (розряд, який змінився, взятий в дужки) Тоді приймач сформує перевірочні розряди К коду Геммінга згідно з Таблицею 2 Таблиця 2 n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 n14 n15 n16 n17 n18 n19 n20 n21  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1  0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0  0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1  0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0  1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1  k1 k2 i3 k4 i5 i6 i7 k8 i9 i10 i11 i12 i13 i14 i15 k16 i17 i18 i19 i20 i21  0 0 (1) 0 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1   К1= i3#i5#i7#i9#i11#i13#i15#i17#i19#i21=(1)#0#1#1#0#0#1#1#1#1=1 К2=i3#i6#i7#i10#i11#i14#i15#i18#i19=(1)#1#1#0#0#0#1#0#1=1 К4=i5#i6#i7#i12#i13#i14#i15#i20#i21=0#1#1#0#0#0#1#0#1=0 К8=i9#i10#i11#i12#i13#i14#i15=1#0#0#0#0#0#1=0 К16=i17#i18#i19#i20#i21=1#0#0#1#1=1 Схема порівняння порозрядно порівнює коди К і k за допомогою операції додавання за модулем 2 K#k =(K16#k16)(K8#k8)(K4#k4)(K2#k2)(K1#k1)= (1#1)(0#0)(0#0)(1#0)(1#0)=00011 Якщо отриманий чотири розрядний код дорівнює 0000, то інформація передалася без помилок. Будь-який інший код вказує на номер розряду, який передався з помилкою( у даному прикладі 00011(2) =3(10) ). 1.6 Для послідовності 16-кових цифр (1ц1л)(2ц1л)(1ц2л)(2ц...